package main.leetcode.offer.firstround.from03to50;

import main.datastruc.TreeNode;

import java.util.*;

/**
 * 32-I.从上到下打印二叉树
 *
 * <p>从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
 *
 * <p>
 *
 * <p>提示：节点总数 <= 1000
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/cong-shang-dao-xia-da-yin-er-cha-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class ex32I {

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
        root.left = new TreeNode(1);
        root.right = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right.right = new TreeNode(4);
        System.out.println(Arrays.toString(new ex32I().levelOrder(root)));
    }

    // 使用辅助队列
    public int[] levelOrder(TreeNode root) {
        if (root == null) return new int[0];
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> list = new ArrayList<>();
        queue.add(root);
        TreeNode node;
        while (!queue.isEmpty()) {
            node = queue.poll();
            list.add(node.val);
            if (node.left != null) queue.add(node.left);
            if (node.right != null) queue.add(node.right);
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < res.length; i++) res[i] = list.get(i);
        return res;
    }

    // 不使用辅助队列
    public int[] levelOrder1(TreeNode root) {
        if (root == null) return new int[0];
        List<TreeNode> list = new ArrayList<>();
        int i = 0;
        list.add(root);
        TreeNode node;
        while (i < list.size()) {
            node = list.get(i);
            if (node.left != null) list.add(node.left);
            if (node.right != null) list.add(node.right);
            i++;
        }
        int[] res = new int[list.size()];
        for (i = 0; i < res.length; i++) res[i] = list.get(i).val;
        return res;
    }
}
